package com.mzy.linear_struct.hot100.动态规划;

import com.mzy.linear_struct.hot100.栈.Pro739每日温度;

import java.util.Arrays;

/**
 * @Author: mizy3
 * @Date: 2024/08/11/下午6:08
 * @Description:
 */
public class Pro509斐波那契数列 {

    public int fib(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        // 确认dp数组及其下标含义
        int[] dp = new int[2];
        // 递推公式 -> dp[n] = dp[i - 1] + dp[i - 2]
        // dp数组如何初始化 -> dp[0] = 1, dp[1] = 1
        dp[0] = 0;
        dp[1] = 1;

        // 遍历顺序 -> 从前往后
        for (int i = 2; i <= n; i++) {

            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
            System.out.println(Arrays.toString(dp));

        }
        // 打印数组
        return dp[1];
    }



/*    public int fib(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        // 确认dp数组及其下标含义
        int[] dp = new int[n + 1];
        // 递推公式 -> dp[n] = dp[i - 1] + dp[i - 2]
        // dp数组如何初始化 -> dp[0] = 1, dp[1] = 1
        dp[0] = 0;
        dp[1] = 1;

        // 遍历顺序 -> 从前往后
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];

        }
        // 打印数组
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }*/


    public static void main(String[] args) {
        new Pro509斐波那契数列().fib(3);
    }
}
